package com.hanxiaozhang.tree.binarytreerecursion;

import com.hanxiaozhang.tree.BinaryTreeTopic;
import com.hanxiaozhang.tree.BinaryTreeUtil;
import com.hanxiaozhang.tree.Node;

import java.util.LinkedList;

/**
 * 〈一句话功能简述〉<br>
 * 〈给定一棵二叉树的头节点head，返回这颗二叉树中是不是完全二叉树〉
 *
 * @author hanxinghua
 * @create 2021/10/30
 * @since 1.0.0
 */
public class IsCBT {

    public static void main(String[] args) {
        int maxLevel = 5;
        int maxValue = 100;
        int testTimes = 1000000;
        for (int i = 0; i < testTimes; i++) {
            Node head = generateRandomBST(maxLevel, maxValue);
            if (isCBT1(head) != isCBT2(head)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }

    /**
     * 方法1
     *
     * @param head
     * @return
     */
    public static boolean isCBT1(Node head) {
        if (head == null) {
            return true;
        }
        LinkedList<Node> queue = new LinkedList<>();
        // 是否遇到过左右两个孩子不双全的节点
        boolean leaf = false;
        Node l = null;
        Node r = null;
        queue.add(head);
        // 宽度优先遍历
        while (!queue.isEmpty()) {
            head = queue.poll();
            l = head.left;
            r = head.right;
            // 如果遇到了不双全的节点之后，又发现当前节点不是叶节点
            if ((leaf && !(l == null && r == null)) ||
                            // 有右，无左
                            (l == null && r != null)) {
                return false;
            }
            if (l != null) {
                queue.add(l);
            }
            if (r != null) {
                queue.add(r);
            }
            if (l == null || r == null) {
                leaf = true;
            }
        }
        return true;
    }

    /**
     * 方法2
     *
     * @param head
     * @return
     */
    public static boolean isCBT2(Node head) {
        if (head == null) {
            return true;
        }
        return process(head).isCBT;
    }


    public static Info process(Node head) {
        if (head == null) {
            return new Info(true, true, 0);
        }
        Info leftInfo = process(head.left);
        Info rightInfo = process(head.right);
        // 高度
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        // 是否满二叉树
        boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;
        boolean isCBT = false;
        // 满二叉树一定是完全二叉树
        if (isFull) {
            isCBT = true;
        } else {
            // 左右都是完全二叉树
            if (leftInfo.isCBT && rightInfo.isCBT) {
                // 左树完全 右树满 左树比右树的高度大1
                if (leftInfo.isCBT && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
                    isCBT = true;
                }
                // 左树满 右满 左树比右树的高度大1
                if (leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
                    isCBT = true;
                }
                // 左树满 右树完全 左树与右树的高度相等
                if (leftInfo.isFull && rightInfo.isCBT && leftInfo.height == rightInfo.height) {
                    isCBT = true;
                }
            }
        }
        return new Info(isFull, isCBT, height);
    }


    /**
     * 实体
     */
    public static class Info {
        // 是否满
        public boolean isFull;
        // 是否完全
        public boolean isCBT;
        // 高度
        public int height;

        public Info(boolean full, boolean cbt, int h) {
            isFull = full;
            isCBT = cbt;
            height = h;
        }
    }

    // for test
    public static Node generateRandomBST(int maxLevel, int maxValue) {
        return BinaryTreeUtil.generate(1, maxLevel, maxValue);
    }


}
